package innersort.insert;

import innersort.speed.SortStrategy;

import java.util.Arrays;

/**
 * @ author : HyoJoo-W
 * @ createDate : 2021-06-03 15:52
 * @ Description :
 */
public class InsertSort implements SortStrategy
{
    public static void main(String[] args)
    {
        int[] array = {-2, 3, 9, -1, 10, 20};
        new InsertSort().insertSort(array);
    }

    @Override
    public void sort(int[] array)
    {
        insertSort(array);
    }

    //升序
    public void insertSort(int[] array)
    {
        int insertVal = 0;//待插入的值
        int insertIndex = 0;//前一个数的索引

        //总共需要插入 n-1 次
        for (int i = 1; i < array.length; i++)
        {
            insertVal = array[i];//待插入的值
            insertIndex = i - 1;//前一个数的索引

            while (insertIndex >= 0 && insertVal < array[insertIndex])
            {
                array[insertIndex + 1] = array[insertIndex];
                insertIndex--;
            }

            if (insertIndex + 1 != i)
            {
                array[insertIndex + 1] = insertVal;
            }

            System.out.println("第" + i +"轮插入后的序列为:" + Arrays.toString(array));
        }
    }


}
